#include <vector>
#include <iostream>

using namespace std;

class Solution {
private:
    int dfs(vector<vector<int>>& matrix, vector<vector<int>>& len_matrix, int i, int j) {
        if (len_matrix[i][j] != 0) {
            return len_matrix[i][j];
        }
        int len = 1;
        if (i > 0 && matrix[i - 1][j] > matrix[i][j]) {
            len = max(len, 1 + dfs(matrix, len_matrix, i - 1, j));
        }
        if (i < matrix.size() - 1 && matrix[i + 1][j] > matrix[i][j]) {
            len = max(len, 1 + dfs(matrix, len_matrix, i + 1, j));
        }
        if (j > 0 && matrix[i][j - 1] > matrix[i][j]) {
            len = max(len, 1 + dfs(matrix, len_matrix, i, j - 1));
        }
        if (j < matrix[0].size() - 1 && matrix[i][j + 1] > matrix[i][j]) {
            len = max(len, 1 + dfs(matrix, len_matrix, i, j + 1));
        }
        len_matrix[i][j] = len;
        return len;
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return 0;
        }
        vector<vector<int>> len_matrix(matrix.size(), vector<int>(matrix[0].size(), 0));
        int height = matrix.size();
        int width = matrix[0].size();
        int max_len = 0;
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                max_len = max(max_len, dfs(matrix, len_matrix, i, j));
            }
        }
        return max_len;
    }
};

int main() {
    vector<vector<int>> input = {
            {1, 2}};
    Solution solution;
    int output = solution.longestIncreasingPath(input);
    cout << output << endl;
}